ON LOGIC ALGEBRA FORMULAS’ COMPLEXITY IN SOME COMPLETE BASES CONSISTING OF ELEMENTS WITH BOTH DIRECT AND ITERATIVE INPUTS 

Lozhkin Sergey Andreevich, Doctor of physical and mathematical sciences, professor, sub-department of mathematical cybernetics, Moscow State University named after M. V. Lomonosov (1 Leninskie gory street, Moscow, Russia), lozhkin@cs.msu.ru
Konovodov Vladimir Aleksandrovich, Postgraduate student, Moscow State University named after M. V. Lomonosov (1 Leninskie gory street, Moscow, Russia), vkonovodov@gmail.com

519.714

Background. One of the main problems in mathematical cybernetics is the problem of control systems synthesis, consisting in building of a circuit from a given class that will realize a given Boolean function. At solving of the problem one often needs to take into account various limitations of control systems’ structure and parameters. Such limitations often describe real calculations more precisely and have a physical interpretation. Moreover, the studies of the complexity of realization of Boolean functions in models with limitations and the effects of limitation parameters are of great theoretical interest. In the present work the limitation is associated with methods of gates connection in a circuit. Circuit elements’ inputs are divided into 2 types – direct and iterative. Iterative inputs are used for connection of other elements’ outputs to them, and direct inputs serve as circuits’ inputs. The synthesis problem in this model is considered for a case of formulas, i.e. circuits without elements’ inputs branching. The aim of the work is to obtain asymptotics of the Shannon function for the complexity of the formulas in the class of complete bases, whose iterative closure contains the class of monotonic functions. In such bases, as it has been previously obtained, the order of growth of this function is "standard" for Boolean formulas, however, the constant in the asymptotics hasn’t been revealed.
Matherials and methods. In this work in particular the authors show the modification of the previously known optimal method of formulas synthesis using the technique of logic-algebra functions modeling by variables on components of special partitions of multiple sets of the Boolean cube.
Results. The authors revealed an asymptotic behavior of the Shannon function for the complexity of Boolean formulas in complete bases with direct and iterative variables, whose iterative closure contains the class of all monotonic functions. The method of finding the constant in the asymptotics was also specified.
Conclusions. The established results allow to conclude about the existence of the asymptotic behavior of the Shannon function for formulas in separate classes of bases with direct and iterative variables, where the order of this function is "standard", and coincides with the order of growth of the corresponding functions for a class of Boolean formulas in regular full bases.

Boolean formulae, direct and iterative variables, synthesis, complexity, Shannon function.

1. Lozhkin S. A. Vestnik Moskovskogo universiteta. Ser. 15: Vychislitel'naya matematika i kibernetika [Bulletin of Moscow State University. Series 15: Calculus mathematics and cybernetics]. 1999, no. 3, pp. 35–41.
2. Lozhkin S. A. Diskretnye modeli v teorii upravlyayushchikh sistem: tr. III Mezhdunar. konf. (Krasnovidovo, 22–28 iyunya 1998 g.) [Discrete models in the theory of control systems: proceedings of III International conference. (Krasnovidovo, 22–28 June 1998)]. Moscow: Dialog-MGU, 1998, pp. 72–73.
3. Konovodov V. A. Uchenye zapiski Kazanskogo universiteta. Ser. Fiziko-matematicheskie nauki [Proceedings of Kazan University. Sereis: Physical and mathematical sciences]. 2014, vol. 156, no. 3, pp. 76–83.
4. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku [Introduction into discrete mathematics]. Moscow: Nauka, 1986, 384 p.
5. Lozhkin S. A. Lektsii po osnovam kibernetiki [Lectures on basic cybernetics]. Moscow:MAKS Press,2004,256p.
6. Lozhkin S. A. Vestnik Moskovskogo universiteta. Ser. 1: Matematika i mekhanika [Bulletin of Moscow University. Series 1: Mathematics and mechanics]. 2007, no. 3, pp. 19–25.